package com.noob.leetcode;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 我们从二叉树的根节点 root 开始进行深度优先搜索。
 *
 * 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
 *
 * 如果节点只有一个子节点，那么保证该子节点为左子节点。
 *
 * 给出遍历输出 S，还原树并返回其根节点 root。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 输入："1-2--3--4-5--6--7"
 * 1-> 0 /2->1/3->2/4->2/5->1/6->2/7->2
 * 输出：[1,2,5,3,4,6,7]
 *
 * 输入："1-401--349---90--88"
 * 输出：[1,401,null,349,88,90]
 *
 */
public class RecoverFromPreorder {


    public static TreeNode recoverFromPreorder(String s){
        //covert map
        Map<Integer, Integer> treeDeepDataMap = convertMap(s);
        TreeNode rootNode=new TreeNode();
        for (Map.Entry<Integer, Integer> entry : treeDeepDataMap.entrySet()) {
            Integer num = entry.getKey();
            Integer deep = entry.getValue();
            TreeNode newNode=new TreeNode(num);
            //处理root节点
            if (deep==0){
                rootNode=newNode;
            }else { //处理其他节点
                TreeNode parent = findParent(rootNode, deep - 1);
                if (parent.left==null){
                    parent.left=newNode;
                }else {
                    parent.right=newNode;
                }
            }
        }
        return rootNode;
    }

    public static TreeNode findParent(TreeNode rootNode,int deep){
        if (deep==0){
            return rootNode;
        }else {
            TreeNode child = rootNode.right;
            if (child==null){
                child= rootNode.left;
            }
            return findParent(child,--deep);
        }
    }


    public static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int x){
            val=x;
        }
        public TreeNode(){
        }
    }

    public static Map<Integer,Integer> convertMap(String s){
        Map<Integer,Integer> treeDeep=new LinkedHashMap<Integer, Integer>();
        int deep=0;
        StringBuffer numStr=new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if ('-'==(s.charAt(i))){
                if (numStr.length()>0){
                    treeDeep.put(Integer.parseInt(numStr.toString()),deep);
                    deep=0;
                    numStr=new StringBuffer();
                }
                deep++;
            }else {
                numStr.append(s.charAt(i));
            }
            if (i==s.length()-1){
                treeDeep.put(Integer.parseInt(numStr.toString()),deep);
            }
        }
        return treeDeep;
    }

}

